package com.annvcit.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;

import com.annvcit.util.AdjMatrix;
import com.annvcit.util.Loader;


/**
 * @author annvcit
 * @full_name Nguyen Van Chuc An
 * @date_created Dec 16, 2014
 * @email annvcit@gmail.com
 */
public abstract class AGraph {
	
	protected int[][] adjMtrx;
	protected int verties;
	
	public AGraph(String fileName) {
		AdjMatrix am = Loader.load(fileName, Loader.LOAD_INT_MATRIX);
		adjMtrx = am.getIntMtrx();
		verties = am.getnOfVerties();
	}

	public AGraph (int[][] am, int verties) {
		this.adjMtrx = am;
		this.verties = verties;
	}
	
	public int[][] getAdjMtrx() {
		return this.adjMtrx;
	}
	
	// tính số cạnh của đồ thị
	public abstract int edges();
	
	// kiểm tra xem có đường đi giữa 2 đỉnh cho trước
	public boolean isHasPath(int v1, int v2) {
		boolean[] visited = new boolean[verties];
		Stack<Integer> stack = new Stack<>();
		int dinhKe;
		
		visited[v1] = true;
		stack.add(v1);
		
		while (true) {
			dinhKe = -1;
			// tìm đỉnh kề của v1
			for (int i = 0; i < verties; i++) {
				if (adjMtrx[v1][i] != 0 && !visited[i]) {
					dinhKe = i;
					v1 = i;
					visited[dinhKe] = true;
					stack.add(dinhKe);
					break;
				}
			} // end for
			
			// sau mỗi lần tìm thấy đỉnh kề thì kiểm tra xem phải là v2 không
			if (dinhKe == v2) return true;
			
			// trường hợp không tìm thấy dinhKe nào
			if (dinhKe == -1) {
				// stack chưa empty thì pop ra
				if (!stack.isEmpty()) {
					v1 = stack.pop();
				} else {
					// không còn gì trong stack nữa thì stop program
					break;
				}
			}
		} // end while
		return false;
	}
	// xóa 1 cạnh nối 2 đỉnh v1 và v2
	public abstract void removeEdge(int v1, int v2);
	
	// In tất cả các đường đi sơ cấp từ v1 tới v2
	public List<StringBuilder> printAllPrimaryPath(int v1, int v2) {
		/*trong quá trình làm có thể v1 được gán cho 1 đỉnh khác, 
		 * nên khi bắt đầu vòng while mới, v1 sẽ được gán lại*/
		int temp = v1; 
		List<StringBuilder> paths = new ArrayList<>();
		/* điều kiện dừng  vòng while 
		 *  hoặc là hết cạnh trong G
		 *  hoặc là v1 là đỉnh cô lập
		 *  */
		while (edges() > 0) {
			StringBuilder primaryPath = new StringBuilder();
			boolean[] visited = new boolean[verties];
			Stack<Integer> stack = new Stack<>();
			int dinhKe;
			v1 = temp;
			
			// kiểm tra xem v1 có phải là đỉnh cô lập hay không
			int counter = 0;
			for (int i = 0; i < verties; i++) {
				if (adjMtrx[v1][i] > 0) counter++;
			}
			if (counter == 0) break;
			
			visited[v1] = true;
			stack.add(v1);
			primaryPath.append(v1);
			
			while (true) {
				dinhKe = -1;
				// tìm đỉnh kề của v1
				for (int i = 0; i < verties; i++) {
					if (adjMtrx[v1][i] != 0 && !visited[i]) {
						dinhKe = i;
						removeEdge(v1, i);
						v1 = i;
						visited[dinhKe] = true;
						stack.add(dinhKe);
						primaryPath.append(dinhKe);
						break;
					}
				} // end for
				
				// sau mỗi lần tìm thấy đỉnh kề thì kiểm tra xem phải là v2 không
				if (dinhKe == v2) {
					/* 
					 * vì có bước (*) nên có thể không có đỉnh v1 trong primaryPath.
					 * và vì v1 luôn ở đầu path nên kiểm tra v1 có hay ko, nếu không
					 * thì insert vào.
					 * */
					if (Integer.parseInt(primaryPath.charAt(0) + "") != temp) { 
						primaryPath.insert(0, temp);
					}
					paths.add(primaryPath);
					break;
				}
				
				// trường hợp không tìm thấy dinhKe nào
				if (dinhKe == -1) {
					// stack chưa empty thì pop ra
					if (!stack.isEmpty()) {
						v1 = stack.pop();
						primaryPath.deleteCharAt(primaryPath.length() - 1); // (*)
					} else {
						// không còn gì trong stack nữa thì stop program
						break;
					}
				}
			}
		} // end while
		return paths;
	}
	
	// kiểm tra đồ thị con
	public boolean isSubGraph(AGraph parent) {
		for (int i = 0; i < verties; i++) {
			if (!cungTinhChatKe(i, adjMtrx, parent.getAdjMtrx())) {
				return false;
			}
		}
		return true;
	}
	
	// kiểm tra với đỉnh v1, ứng với mỗi cạnh trong đồ thị con 
	// thì bên đồ thị cha có như thế hay không
	private boolean cungTinhChatKe(int v1, int[][] childAdjMtrx, int[][] parentAdjMtrx) {
		for (int i = 0; i < verties; i++) {
			if (childAdjMtrx[v1][i] > 0 && !(parentAdjMtrx[v1][i] > 0)) {
				// tức là đồ thị con có v1 kề với i mà đồ thị cha không có
				return false;
			}
		}
		return true;
	}
	
	// depth first search
	public StringBuilder dfs() {
		StringBuilder dfsPath = new StringBuilder(); 
		boolean[] visited = new boolean[verties];
		Stack<Integer> stack = new Stack<>();
		int dinhKe;
		// chọn 1 đỉnh bắt đầu
		Random rd = new Random();
		int v1 = rd.nextInt(verties);
		
		visited[v1] = true;
		stack.push(v1);
		dfsPath.append(v1);
		
		while (true) {
			dinhKe = -1;
			// tìm đỉnh kề của v1
			for (int i = 0; i < verties; i++) {
				if (adjMtrx[v1][i] != 0 && !visited[i]) {
					dinhKe = i;
					v1 = i;
					visited[dinhKe] = true;
					stack.add(dinhKe);
					dfsPath.append(dinhKe);
					break;
				}
			} // end for
			
			// trường hợp không tìm thấy dinhKe nào
			if (dinhKe == -1) {
				// stack chưa empty thì pop ra
				if (!stack.isEmpty()) {
					v1 = stack.pop();
				} else {
					// không còn gì trong stack nữa thì stop program
					break;
				}
			}
		}
		return dfsPath;
	}
	
	public StringBuilder bfs() {
		Queue<Integer> queue = new PriorityQueue<>();
		StringBuilder bfsPath = new StringBuilder();
		boolean[] visited = new boolean[verties];
		// chọn một đỉnh bắt đầu
		Random rd = new Random();
		int v1 = rd.nextInt(verties);
		
		queue.add(v1);
		visited[v1] = true;
		bfsPath.append(v1);
		
		int v2;
		int counter;
		while (queue.size() > 0) {
			counter = 0;
			for (int i = 0; i < visited.length; i++) {
				if (visited[i]) counter++;
			}
			
			if (counter == visited.length) break;
			v2 = queue.remove();
			for (int i = 0; i < verties; i++) {
				if (adjMtrx[v2][i] > 0 && !visited[i]) {
					queue.add(i);
					visited[i] = true;
					bfsPath.append(i);
				}
			}
		} // end while
		return bfsPath;
	}
}
